class Solution(object):
    def prisonAfterNDays(self, cells, n):
        d = {}
        index = 0
        while tuple(cells) not in d and index < n:
            d[tuple(cells)] = index
            index += 1
            next_cells = [0] * 8
            for i in range(1, 7):
                if cells[i - 1] and cells[i + 1]:
                    next_cells[i] = 1
                if (not cells[i - 1]) and (not cells[i + 1]):
                    next_cells[i] = 1
            cells = next_cells
        if index == n:
            return cells
        start = d[tuple(cells)]
        T = index - start
        index = (n - start) % T + start
        for key in d:
            if d[key] == index:
                return list(key)



data = Solution()
cells = [0, 1, 0, 1, 1, 0, 0, 1]
n = 7
print(data.prisonAfterNDays(cells, n))
